package org.example;

public class Test1 {
    //leetcode 494 目标和 https://leetcode.cn/problems/target-sum/description/
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length, sum = 0;
        for (int num : nums) sum += num;
        int halfSum = (sum + target) / 2;
        if (Math.abs(target) > sum || (sum + target) % 2 == 1) return 0;
        //dp[i][j]表示从前i哥物品中挑选物品使得背包中的物品的和为j有几种挑选方式
        int[][] dp = new int[n + 1][halfSum + 1];
        //初始化，dp[0][0]表示从前0个物品中挑选使得背包中的和为0，也就是什么都不选，有一种方式
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= halfSum; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= nums[i-1]) dp[i][j] += dp[i-1][j-nums[i-1]];
            }
        }
        return dp[n][halfSum];
    }

    //优化
    public int findTargetSumWays1(int[] nums, int target) {
        int n = nums.length, sum = 0;
        for (int num : nums) sum += num;
        int halfSum = (sum + target) / 2;
        if (Math.abs(target) > sum || (sum + target) % 2 == 1) return 0;
        //dp[i][j]表示从前i哥物品中挑选物品使得背包中的物品的和为j有几种挑选方式
        int[] dp = new int[halfSum + 1];
        //初始化，dp[0][0]表示从前0个物品中挑选使得背包中的和为0，也就是什么都不选，有一种方式
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = halfSum; j >= nums[i-1]; j--) {
                dp[j] += dp[j-nums[i-1]];
            }
        }
        return dp[halfSum];
    }
}
